The present invention is directed to a method of detecting images compressed in accordance with the conventional JPEG image compression standard, and more particularly, a method of detection a blocking signature in an image to provide identification of a JPEG compressed image.
Data compression is required in data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, where the time to transmit is long, or where bandwidth is limited. Another use for compression is in data storage, where the amount of media space on which the data is stored can be substantially reduced with compression. A device showing either or both of these cases is a digital copier where an intermediate storage is used for collation, reprint or any other digital copier functions. Additionally, digital copiers often allow the printing of externally received data. Generally speaking, scanned images and print masters, i.e., electronic representations of hard copy documents, are commonly large, and thus are desirable candidates for compression.
The method disseminated by the JPEG committee for still image compression is described in detail in xe2x80x9cJPEG: Still Image Compression Standardxe2x80x9d, by W. Pennebaker and J. Mitchell, published by Van Nostrand Reinhold in 1992. We will refer to the lossy compression modes based on the discrete cosine transform and it will be called JPEG compression in this application. JPEG compression is a lossy system that reduces data redundancies based on pixel to pixel correlations. Generally, in images, on a pixel to pixel basis, an image does not change very much. An image therefore has what is known as xe2x80x9cnatural spatial correlationxe2x80x9d. In natural scenes, correlation is generalized, but not exact. Noise makes each pixel somewhat different from its neighbors.
Generally, as shown in FIG. 1, a JPEG compression and decompression system is illustrated. A more complete discussion may be had by referencing U.S. Pat. No. 5,321,522 to Eschbach and U.S. Pat. No. 5,359,676 to Fan. The entire contents of U.S. Pat. No. 5,321,522 and U.S. Pat. No. 5,359,676 are hereby incorporated by reference.
Initially provided is tile memory 10 for storing an Mxc3x97M portion of the image. From the portion of the image stored in tile memory, the discrete cosine transform (DCT), transformer 12 forms a frequency space representation of the image. Hardware implementations are available, such as the C-Cube Microsystems CL550A JPEG image compression processor, which operates in either the compression or the decompression mode according to the proposed JPEG standard. As will be described below, the implementation of the invention can be in either in software or hardware.
A divisor/quantization device 14 is used, from a set of values referred to as a Q-Table, stored in a Q table memory 16, so that a distinct Q table value is divided into the DCT value, returning the integer portion of the value as the quantized DCT value. A statistical encoder 20 often using Hufftman codes is used to endcode the quantized DCT values to generate the compressed image that is output for storage, transmission, etc.
Discrete cosine transforms are well known, and hardware exists to perform the transform on image data, e.g., U.S. Pat. No. 5,049,991 to Niihara, U.S. Pat. No. 5,001,559 to Gonzales et al., and U.S. Pat. No. 4,999,705 to Puri.
To decompress the now-compressed image, and with reference to FIG. 1, a series of functions or steps are followed to reverse the process described. Huffman encoding is removed at decoder 50. The image signal now represents the quantized DCT coefficients, which are multiplied at signal multiplier 52 by the Q table values in memory 54 in a process inverse to the compression process. At inverse transformer 56, the inverse transform of the discrete cosine transform is derived, and the output image in the spatial domain is stored at image buffer 58.
In U.S. Pat. No. 5,321,522 and U.S. Pat. No. 5,379,122 to Eschbach, U.S. Pat. No. 5,359,676 to Fan, the standard process described in FIG. 1 is varied. The original image is compressed; the compressed representation is decompressed. The decompressed image is additionally filtered to improve appearance, but in doing so, it may be forced outside the range of images that are possibly derived from the original image. The DCT representation of the image is therefore altered, in order to force the image into the acceptable range of images. The processes may be used iteratively.
Some image formats that involve compression such those using JPEG inflict degradation to the image. When a system invokes to print one of these compressed images, the incoming image may receive special processing to remove those artifacts. First, however, one has to determine whether the image was compressed beforehand.
The present invention proposes a method to identify whether the image was compressed in the past. Moreover, the present invention proposes a method to identify whether the image was JPEG compressed in the past. By enabling identification of compressed images, the present invention will enable the printing system to steer a compressed image towards a cleaning image processing operation, thereby enabling the printing system to clean-up the image from any undesirable artifacts.
The method of the present invention is based on the analysis of subtle blocking discontinuities that are present and readily discernible in compressed images. For example in producing JPEG compressed images, the image is divided into blocks that are transformed, quantized, and compressed virtually independently. Thus, discontinuities across block boundaries (blocking effects) account for the most noticeable compression artifact caused by JPEG compression. The higher the compression the higher the blocking. The present invention performs an analysis of the blocking discontinuities as an indicative of compression history.
One aspect of the present invention is a method for detecting if an image is compressed. The method computes the absolute difference between two neighbor pixels of an image, for a predetermined number of pixels of the image, horizontally and vertically; divides the results into first differences that correspond to crossing block boundaries (I) and second differences that correspond to not crossing block boundaries (II); computes histograms from samples in I and II; normalizes each histogram; and determines if the image is compressed based on a difference between the two normalized histograms.
A second aspect of the present invention is a method for detecting if an image is compressed. The method determines a block grid within the image; establishes blocks from the determined grid; computes differences between samples inside the established blocks; computes differences between samples across the established blocks; and determines that the image is compressed based on characteristics derived from statistics of the computed differences.
A third aspect of the present invention is a method of determining if an image is compressed. The method determines a block grid within the image; establishes blocks from the determined grid; for each block, computes a first set of differences from four adjacent pixels located within the block; for each block, computes a second set of differences from four adjacent pixels, each pixel being located in a corner of four adjacent blocks; computes histogram H(n) for the first set of differences and histogram Hxe2x80x2 (n) for the second set of differences; normalizes the histograms; and determines if the image is compressed based on a difference between the two normalized histograms.
A fourth aspect of the present invention is a method of determining if an image is compressed. The method determines a block grid within the image; establishes blocks from the determined grid; for each block, computes a first set of differences from a first set of four adjacent pixels located within the block; for each block, computes a second set of differences from a second set of four adjacent pixels located within the block; for each block, computes a third set of differences from a third set of four adjacent pixels, each pixel in the third set being located in a corner of four adjacent blocks; computes histogram H0(n) for the first set of differences, histogram, histogram H1(n) for the second set of differences, and histogram Hxe2x80x2 (n) for the third set of differences; normalizes the histograms; and determines if the image is compressed based on a difference between the three normalized histograms.
A fifth aspect of the present invention is a method for determining a grid within an image. The method computes a first sum of absolute values of the differences in a horizontal direction comprising only samples which are a predetermined number of pixels apart; computes a second sum of absolute values of the differences in a vertical direction comprising only samples which are the predetermined number of pixels apart; and determines if the image contains a grid based on a relationship between the first and second sums and a predetermined threshold.
A sixth aspect of the present invention is a method for determining a grid location within an image. Let P(i,j) be the light intensity of image pixels at position (i,j) in the image. The method computes a first sum EH of absolute values of the differences in a horizontal direction comprising only samples that are a predetermined number of pixels R apart wherein
EH=xcexa3ixcexa3j|P(i,Rj+DH)xe2x88x92P(i,Rj+DHxe2x88x921)|;
computes a second sum Ev of absolute values of the differences in a vertical direction comprising only samples which are a predetermined number of pixels R apart wherein
Ev=xcexa3ixcexa3j|P(Ri+Dv,j)xe2x88x92P(Ri+Dvxe2x88x921,j)|;
determines if the image contains a grid based on a relationship between the first and second sums and a predetermined threshold; and locates a boundary in the R-pixel-spaced grid as a point vertically shifted by Dv pixels from an origin and horizontally shifted by DH pixels from the origin, wherein Dv and DH are values which maximize Ev and EH, respectively.
Another aspect of the present invention is a method for detecting if an image is compressed. The method computes the absolute difference between two neighbor pixels of an image, for a predetermined number of pixels of the image, horizontally and vertically; divides the results into first differences that correspond to crossing block boundaries (I) and second differences that correspond to not crossing block boundaries (II); and determines if the image is compressed based on a difference between statistics of the first and second difference sequences.
A further aspect of the present invention is a method to detect if an image is compressed. The method detects blocking artifacts in the image indicative of compression and provides an output indicative of compression upon detection of the blocking artifacts.
Further objects and advantages of the present invention will become apparent from the following description and the various features of the present invention.